5880. МEX

Знаешь, как это сложно — нажать на курок?

Знаменитый диктатор Ли Сий Сын располагает армией численностью в 10⁵ человек. Он пронумеровал их от 0 до 10⁵ – 1: чем меньше номер, тем выше командирские способности солдата. Позже он репрессировал n человек. Теперь диктатор собирается провести маленькую победоносную войну с соседним государством, поэтому ему необходимо срочно выбрать самого талантливого из оставшихся в живых военных.

Вход. В первой строке задано количество репрессированных n (1 ≤ n < 10⁵). Во второй строке приведены их номера в списке Ли Сий Сына – все числа меньше 10⁵.

Выход. Выведите одно число – номер самого талантливого из оставшихся в живых военных.

Пример входа	Пример выхода
8 3 0 1 7 2 4 6 17	5

РЕШЕНИЕ

сортировка подсчетом

Анализ алгоритма

Пусть cnt – целочисленный массив длины 10⁵. Для каждого значения x из входного списка репрессированных установим cnt[x] = 1.

Затем нужно найти наименьший индекс i, для которого cnt[i] = 0. Это число и является минимальным из тех, что отсутствуют во входных данных. Именно i будет номером самого талантливого из оставшихся в живых военных.

Пример

Рассмотрим состояние массива cnt после обработки всех данных входного теста.

Наименьшим числом, отсутствующим во входном массиве, будет 5, поскольку cnt[5] = 0.

Реализация алгоритма

Объявим массив для подсчёта номеров, которые встречаются во входных данных.

#define MAX 100001

int cnt[MAX];

Читаем входные данные. Для каждого значения x из списка репрессированных устанавливаем cnt[x] = 1.

scanf("%d", &n);

for (i = 0; i < n; i++)

{

scanf("%d", &x);

cnt[x] = 1;

}

Далее ищем наименьшее неотрицательное целое число, отсутствующее во входном списке. Для этого нужно найти минимальное i (i ≥ 0), для которого cnt[i] = 0.

for (i = 0; i < MAX; i++)

if (cnt[i] == 0)

{

printf("%d\n", i);

break;

}